package com.algorithm.分治;

/**
 * 给定一个长度为 n 的整数序列，求它的最大连续子序列和
 * 比如 –2、1、–3、4、–1、2、1、–5、4 的最大连续子序列和是 4 + (–1) + 2 + 1 = 6
 * 这道题也属于最大切片问题(最大区段，Greatest Slice)
 * <p>
 * 概念区分: 子串、子数组、子区间必须是连续的，子序列是可以不连续的
 */
public class 最大连续子序列和 {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums));
    }

    /**
     * 暴力破解最大连续子序列和
     *
     * @param nums
     * @return
     */
    private static int bruteForce(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int maxNum = Integer.MIN_VALUE;
        for (int begin = 0; begin < nums.length; begin++) {
            for (int end = begin; end < nums.length; end++) {
                // sum是begin和end的和
                int sum = 0;
                for (int i = begin; i < end; i++) {
                    sum += nums[i];
                }
                maxNum = Math.max(maxNum, sum);
            }
        }
        return maxNum;
    }

    /**
     * 暴力破解最大连续子序列和（优化）
     *
     * @param nums
     * @return
     */
    private static int bruteForce2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int maxNum = Integer.MIN_VALUE;
        for (int begin = 0; begin < nums.length; begin++) {
            int sum = 0;
            for (int end = begin; end < nums.length; end++) {
                // sum是begin和end的和
                sum += nums[end];
                maxNum = Math.max(maxNum, sum);
            }
        }
        return maxNum;
    }

    /**
     * 使用分治的思想解决最大连续子序列和
     *
     * @param nums
     * @return
     */
    private static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        return maxSubArray(nums, 0, nums.length);
    }
    private static int maxSubArray(int[] nums, int begin, int end) {
        if (end - begin < 2) return nums[begin];
        int mid = (begin + end) >> 1;

        int leftMax = Integer.MIN_VALUE;
        int leftNum = 0;
        for (int i = mid - 1; i >= begin; i--) {
            leftNum += nums[i];
            leftMax = Math.max(leftMax, leftNum);
        }

        int rightMax = Integer.MIN_VALUE;
        int rightNum = 0;
        for (int i = mid; i < end; i++) {
            rightNum += nums[i];
            rightMax = Math.max(rightNum, rightMax);
        }

        return Math.max(
                leftMax + rightMax, Math.max(
                        maxSubArray(nums, begin, mid),
                        maxSubArray(nums, mid, end))
        );
    }
}
